Neden sıralı bir diziyi işlemek, sıralanmamış bir diziyi işlemekten daha hızlıdır?

Şube tahmininin bir kurbanısınız.
Şube Tahmini nedir?
Bir demiryolu kavşağını düşünün:
Mecanismo tarafından, Wikimedia Commons aracılığıyla görüntü. CC-By-SA 3.0 lisansı altında kullanılır.
Şimdi tartışma uğruna, bunun 1800'lü yıllara geri döndüğünü varsayalım - uzun mesafe veya radyo iletişiminden önce.
Bir kavşağın operatörüsünüz ve bir trenin geldiğini duyarsınız. Hangi yöne gitmesi gerektiğine dair hiçbir fikrin yok. Sürücüye hangi yöne gitmek istediklerini sormak için treni durduruyorsunuz. Ve sonra anahtarı uygun şekilde ayarlarsınız.
Trenler ağırdır ve çok fazla ataleti vardır. Bu yüzden başlaması ve yavaşlaması sonsuza kadar sürer.
Daha iyi bir yol var mı? Trenin hangi yöne gideceğini tahmin edin!
Doğru tahmin ettiyseniz, devam ediyor.
Yanlış tahmin ettiyseniz, kaptan duracak, geri dönecek ve düğmeyi çevirmeniz için size bağıracak. Ardından diğer yolu yeniden başlatabilir.
Her seferinde doğru tahmin ederseniz, tren asla durmak zorunda kalmayacak. Çok sık yanlış tahmin ederseniz, tren durmak, yedeklemek ve yeniden başlatmak için çok zaman harcayacaktır.
Bir if ifadesini düşünün: İşlemci düzeyinde, bu bir dallanma talimatıdır:
Sen bir işlemcisin ve bir dal görüyorsun. Hangi yöne gideceğine dair hiçbir fikrin yok. Ne yaparsın? Yürütmeyi durdurur ve önceki talimatlar tamamlanana kadar beklersiniz. Sonra doğru yola devam edersiniz.
Modern işlemciler karmaşıktır ve uzun boru hatlarına sahiptir. Bu yüzden "ısınmaları" ve "yavaşlamaları" sonsuza kadar sürer.
Daha iyi bir yol var mı? Dalın hangi yöne gideceğini tahmin edin!
Doğru tahmin ettiyseniz, uygulamaya devam edersiniz.
Yanlış tahmin ettiyseniz, boru hattını yıkamanız ve şubeye geri dönmeniz gerekir. Ardından diğer yolu yeniden başlatabilirsiniz.
Her seferinde doğru tahmin ederseniz, infazın asla durması gerekmeyecek. Çok sık yanlış tahmin ederseniz, çok fazla zamanınızı oyalayarak, geri çekerek ve yeniden başlatarak harcarsınız.
Bu şube tahminidir. Tren sadece bir bayrakla yönü işaret edebileceği için bunun en iyi benzetme olmadığını kabul ediyorum. Ancak bilgisayarlarda işlemci son ana kadar bir şubenin hangi yöne gideceğini bilemez.
Öyleyse, trenin kaç kez yedeklenmesi ve diğer yola inmesi gerektiğini en aza indirmeyi stratejik olarak nasıl tahmin edersiniz? Geçmişe bakıyorsun! Tren zamanın% 99'unu terk ederse, sanırım sola. Değişirse, tahminlerinizi değiştirirsiniz. Her üç seferde bir yöne giderse, aynı tahmin edersiniz ...
Başka bir deyişle, bir model belirlemeye ve onu takip etmeye çalışırsınız. Bu, az ya da çok dal tahmincilerinin çalışma şeklidir.
Çoğu uygulamanın iyi huylu dalları vardır. Dolayısıyla, modern şube tahmincileri tipik olarak>% 90 isabet oranlarına ulaşacaktır. Ancak, tanınabilir örüntüleri olmayan öngörülemeyen dallarla karşılaşıldığında, dal belirleyicileri neredeyse işe yaramaz.
Daha fazla okuma: Wikipedia'daki "Dal belirleyici" makalesi.
Yukarıdan ima edildiği gibi, suçlu bu if-ifadesidir:
eğer (veri [c]> = 128)
toplam + = veri [c];
Verilerin 0 ile 255 arasında eşit olarak dağıtıldığına dikkat edin. Veriler sıralandığında, iterasyonların kabaca ilk yarısı if ifadesine girmeyecektir. Bundan sonra, hepsi if ifadesini girecek.
Şube art arda birçok kez aynı yöne gittiği için bu, şube tahmincisi için çok dostane bir durumdur. Basit bir doygunluk sayacı bile, yön değiştirdikten sonraki birkaç yineleme dışında dalı doğru bir şekilde tahmin edecektir.
Hızlı görselleştirme:
T = alınan dal
N = dal alınmadı
veri [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
dal = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (tahmin etmesi kolay)
Bununla birlikte, veriler tamamen rastgele olduğunda, dal tahmincisi, rastgele verileri tahmin edemediği için işe yaramaz hale gelir. Bu nedenle muhtemelen% 50 civarında yanlış tahmin olacaktır (rastgele tahmin etmekten daha iyi değildir).
veri [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
dal = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (tamamen rastgele - tahmin etmesi zor)
Peki ne yapılabilir?
Derleyici, dalı koşullu bir hareket halinde optimize edemiyorsa, performans için okunabilirlikten ödün vermek istiyorsanız bazı hack'leri deneyebilirsiniz.
Değiştirin:
eğer (veri [c]> = 128)
toplam + = veri [c];
ile:
int t = (veri [c] - 128) >> 31;
toplam + = ~ t & veri [c];
Bu, dalı ortadan kaldırır ve onu bazı bitsel işlemlerle değiştirir.
(Bu saldırının, orijinal if ifadesine tam olarak eşdeğer olmadığını unutmayın. Ancak bu durumda, verilerin [] tüm giriş değerleri için geçerlidir.)
Karşılaştırmalar: Core i7 920 @ 3.5 GHz
C ++ - Visual Studio 2010 - x64 Sürümü
// Dal - Rastgele
saniye = 11.777
// Dal - Sıralanmış
saniye = 2.352
// Dalsız - Rastgele
saniye = 2,564
// Dalsız - Sıralanmış
saniye = 2,587
Java - NetBeans 7.1.1 JDK 7 - x64
// Dal - Rastgele
saniye = 10.93293813
// Dal - Sıralanmış
saniye = 5,643797077
// Dalsız -Rastgele
saniye = 3,113581453
// Dalsız - Sıralanmış
saniye = 3,186068823
Gözlemler:
Dal ile: Sıralanmış ve sıralanmamış veriler arasında çok büyük bir fark vardır.
Hack ile: Sıralanmış ve sıralanmamış veriler arasında hiçbir fark yoktur.
C ++ durumunda, veri sıralandığında kesmek aslında daldan biraz daha yavaştır.
Genel bir pratik kural, kritik döngülerde (bu örnekte olduğu gibi) verilere bağlı dallanmadan kaçınmaktır.
Güncelleme:
X64 üzerinde -O3 veya -ftree-vectorize ile GCC 4.6.1 koşullu bir hareket oluşturabilir. Dolayısıyla, sıralı ve sıralanmamış veriler arasında hiçbir fark yoktur - her ikisi de hızlıdır.
(Veya biraz hızlı: önceden sıralanmış durum için, özellikle GCC onu sadece eklemek yerine kritik yola koyarsa, özellikle cmov'un 2 döngü gecikmesine sahip olduğu Broadwell'den önce: gcc optimizasyon bayrağı -O3 kodu yavaşlatırsa daha yavaş olabilir -O2'den)
VC ++ 2010, / Ox altında bile bu dal için koşullu hareketler oluşturamaz.
Intel C ++ Compiler (ICC) 11 mucizevi bir şey yapar. İki döngüyü değiştirir, böylece öngörülemeyen dalı dış döngüye doğru kaldırır. Bu nedenle, yalnızca yanlış tahminlere karşı bağışıklığı değil, aynı zamanda VC ++ ve GCC'nin üretebileceğinden iki kat daha hızlıdır! Başka bir deyişle, ICC, ölçütü yenmek için test döngüsünden yararlandı ...
Intel derleyicisine dalsız kodu verirseniz, onu sağdan vektörleştirir ... ve dalda olduğu kadar hızlıdır (döngü değişimi ile).
Bu, olgun modern derleyicilerin bile kodu optimize etme yeteneklerinde çılgınca değişiklik gösterebileceğini gösteriyor ...
|
Dal tahmini.
Sıralanmış bir diziyle, [c]> = 128 koşul verisi, bir dizi değer için önce yanlış, ardından sonraki tüm değerler için doğru olur. Tahmin etmesi kolay. Sıralanmamış bir dizide, dallanma maliyetini ödersiniz.
|
Veriler sıralandığında performansın büyük ölçüde artmasının nedeni, Mysticial'ın cevabında güzel bir şekilde açıklandığı gibi, dal tahmin cezasının kaldırılmasıdır.
Şimdi, koda bakarsak
eğer (veri [c]> = 128)
toplam + = veri [c];
bu özel if ... else ... dalının anlamının, bir koşul karşılandığında bir şeyler eklemek olduğunu bulabiliriz. Bu tür bir dal, kolayca koşullu bir hareket deyimine dönüştürülebilir ve bu, bir koşullu hareket talimatına derlenebilir: bir x86 sisteminde cmovl. Dal ve dolayısıyla olası dal tahmin cezası kaldırılır.
C, dolayısıyla C ++ 'da, x86'daki koşullu hareket talimatına doğrudan (herhangi bir optimizasyon olmaksızın) derlenecek olan ifade, üçlü operatör ...? ...: .... Yani yukarıdaki ifadeyi eşdeğer bir ifadeyle yeniden yazıyoruz:
toplam + = veri [c]> = 128? veri [c]: 0;
Okunabilirliği korurken hızlandırma faktörünü kontrol edebiliriz.
Intel Core i7-2600K @ 3.4 GHz ve Visual Studio 2010 Yayın Modunda karşılaştırma ölçütü (Mysticial'dan kopyalanan format):
x86
// Dal - Rastgele
saniye = 8.885
// Dal - Sıralanmış
saniye = 1.528
// Dalsız - Rastgele
saniye = 3.716
// Dalsız - Sıralanmış
saniye = 3.71
x64
// Dal - Rastgele
saniye = 11.302
// Dal - Sıralanmış
saniye = 1.830
// Dalsız - Rastgele
saniye = 2.736
// Dalsız - Sıralanmış
saniye = 2.737
Sonuç, birden çok testte sağlamdır. Dallanma sonucu tahmin edilemez olduğunda büyük bir hızlanma elde ederiz, ancak tahmin edilebilir olduğunda biraz acı çekeriz. Aslında, koşullu bir hareket kullanılırken, veri modelinden bağımsız olarak performans aynıdır.
Şimdi ürettikleri x86 derlemesini inceleyerek daha yakından bakalım. Basit olması için max1 ve max2 olmak üzere iki fonksiyon kullanıyoruz.
max1 koşullu dalı kullanır if ... else ...:
int max1 (int a, int b) {
eğer (a> b)
dönüş a;
Başka
dönüş b;
}
max2 üçlü operatörü kullanır ...? ...: ...:
int max2 (int a, int b) {
return a> b? a: b;
}
Bir x86-64 makinesinde, GCC -S aşağıdaki derlemeyi oluşturur.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp .L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
ayrılmak
ret
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
ayrılmak
ret
max2 komut cmovge kullanımı nedeniyle çok daha az kod kullanır. Ancak gerçek kazanç, max2'nin, tahmin edilen sonuç doğru değilse önemli bir performans cezasına neden olacak dal atlamaları, jmp içermemesidir.
Öyleyse neden koşullu bir hareket daha iyi performans gösterir?
Tipik bir x86 işlemcide, bir talimatın yürütülmesi birkaç aşamaya bölünmüştür. Kabaca, farklı aşamalarla başa çıkmak için farklı donanımlarımız var. Bu nedenle, yenisini başlatmak için bir talimatın bitmesini beklemek zorunda değiliz. Buna ardışık düzen denir.
Dallanma durumunda, aşağıdaki talimat bir öncekiyle belirlenir, bu nedenle ardışık düzen yapamayız. Ya beklemek ya da tahmin etmek zorundayız.
Koşullu bir hareket durumunda,yürütme koşullu hareket talimatı birkaç aşamaya bölünmüştür, ancak Getirme ve Kod Çözme gibi önceki aşamalar önceki talimatın sonucuna bağlı değildir; sadece sonraki aşamaların sonuca ihtiyacı vardır. Bu nedenle, bir komutun yürütme süresinin bir kısmını bekleriz. Tahmin kolay olduğunda şartlı hareket versiyonunun şubeden daha yavaş olmasının nedeni budur.
Bilgisayar Sistemleri: Bir Programcının Perspektifi kitabı, ikinci baskı bunu ayrıntılı olarak açıklıyor. Koşullu Taşıma Talimatları için Bölüm 3.6.6'ya, İşlemci Mimarisi için Bölüm 4'ün tamamına ve Dal Tahmin ve Yanlış Tahmin Cezalarına yönelik özel muamele için Bölüm 5.11.2'ye bakabilirsiniz.
Bazen, bazı modern derleyiciler daha iyi performansla kodumuzu derlemeye optimize edebilir, bazen bazı derleyiciler bunu yapamaz (söz konusu kod, Visual Studio'nun yerel derleyicisini kullanıyor). Tahmin edilemez olduğunda bir dal ve koşullu hareket arasındaki performans farkını bilmek, senaryo çok karmaşık hale geldiğinde, derleyicinin bunları otomatik olarak optimize edemediği durumlarda daha iyi performansla kod yazmamıza yardımcı olabilir.
|
Bu koda yapılabilecek daha da fazla optimizasyonu merak ediyorsanız, şunu düşünün:
Orijinal döngüden başlayarak:
için (işaretsiz i = 0; i <100000; ++ i)
{
for (işaretsiz j = 0; j  = 128)
toplam + = veri [j];
}
}
Döngü değişimi ile bu döngüyü güvenle şu şekilde değiştirebiliriz:
for (işaretsiz j = 0; j  = 128)
toplam + = veri [j];
}
}
Ardından, if koşulunun i döngüsünün yürütülmesi boyunca sabit olduğunu görebilir, böylece if koşulunu kaldırabilirsiniz:
for (işaretsiz j = 0; j  = 128)
{
için (işaretsiz i = 0; i <100000; ++ i)
{
toplam + = veri [j];
}
}
}
Ardından, kayan nokta modelinin buna izin verdiğini varsayarak, iç döngünün tek bir ifadeye daraltılabileceğini görürsünüz (örneğin, / fp: hızlı atılır)
for (işaretsiz j = 0; j  = 128)
{
toplam + = veri [j] * 100000;
}
}
Bu, öncekinden 100.000 kat daha hızlı.
|
Hiç şüphe yok ki bazılarımız, CPU'nun dal tahmincisi için sorunlu olan kodu tanımlama yollarıyla ilgilenecektir. Valgrind aracı cachegrind, --branch-sim = yes bayrağı kullanılarak etkinleştirilen bir dal tahmin simülatörüne sahiptir. Dış döngü sayısı 10000'e düşürülmüş ve g ++ ile derlenmiş olarak bu sorudaki örnekler üzerinden çalıştırmak şu sonuçları verir:
Sıralandı:
== 32551 == Şubeler: 656,645,130 (656,609,208 koşul + 35,922 ind)
== 32551 == Yanlış Tahminler: 169,556 (169,095 koşul + 461 ind)
== 32551 == Yanlış tahmin oranı:% 0,0 (% 0,0 +% 1,2)
Sınıflandırılmamış:
== 32555 == Dallar: 655,996,082 (655,960,160 koşul + 35,922 ind)
== 32555 == Yanlış Tahminler: 164.073.152 (164.072.692 koşul + 460 ind)
== 32555 == Yanlış tahmin oranı:% 25,0 (% 25,0 +% 1,2)
Söz konusu döngü için gördüğümüz cg_annotate tarafından üretilen çıktıyı satır satır inceleyerek:
Sıralandı:
Bc Bcm Bi Bim
10.001 4 0 0 için (işaretsiz i = 0; i <10000; ++ i)
. . . . {
. . . . // birincil döngü
327.690.000 10.016 0 0 for (işaretsiz c = 0; c  = 128)
0 0 0 0 toplamı + = veri [c];
. . . . }
. . . . }
Sınıflandırılmamış:
Bc Bcm Bi Bim
10.001 4 0 0 için (işaretsiz i = 0; i <10000; ++ i)
. . . . {
. . . . // birincil döngü
327.690.000 10.038 0 0 for (unsigned c = 0; c  = 128)
0 0 0 0 toplamı + = veri [c];
. . . . }
. . . . }
Bu, sorunlu çizgiyi kolayca belirlemenizi sağlar - sıralanmamış sürümde if (data [c]> = 128) satırı, cachegrind'in dallanma tahmin modeli altında 164.050.007 yanlış tahmin edilmiş koşullu dallara (Bcm) neden olurken, sıralı sürümde yalnızca 10.006'ya neden olur .
Alternatif olarak, Linux'ta aynı görevi yerine getirmek için performans sayaçları alt sistemini kullanabilirsiniz, ancak CPU sayaçlarını kullanarak yerel performansla.
performans durumu ./sumtest_sorted
Sıralandı:
"./Sumtest_sorted" için performans sayacı istatistikleri:
11808.095776 görev saati # 0.998 kullanılan CPU
1,062 bağlam anahtarı # 0,090 K / sn
14 CPU geçişi # 0,001 K / sn
337 sayfa hatası # 0,029 K / sn
26.487.882.764 döngü # 2.243 GHz
41,025,654,322 talimat # 1.55 insns döngü başına
6.558.871.379 şube # 555.455 M / sn
567.204 şube kaçırdı Tüm şubelerin% 0.01'i
11.827228330 saniye geçen süre
Sınıflandırılmamış:
Verim"./sumtest_unsorted" için sayaç istatistikleri:
28877.954344 görev saati # 0.998 kullanılan CPU
2,584 bağlam anahtarı # 0,089 K / sn
18 CPU geçişi # 0,001 K / sn
335 sayfa hatası # 0,012 K / sn
65.076.127.595 döngü # 2.253 GHz
41,032,528,741 talimat # 0,63 döngü başına insns
6.560.579.013 şube # 227.183 M / sn
1.646.394.749 şube kaçırdı Tüm şubelerin% 25.10'u
28.935500947 saniye geçen süre
Aynı zamanda demontaj ile kaynak kodu açıklama yapabilir.
performans kaydı -e dal-ıskalar ./sumtest_unsorted
perf annotate -d sumtest_unsorted
Yüzde | Sumtest_unsorted kaynak kodu ve demontajı
------------------------------------------------
...
: toplam + = veri [c];
0,00: 400a1a: mov -0x14 (% rbp),% eax
39.97: 400a1d: mov% eax,% eax
5.31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4,60: 400a26: cltq
0.00: 400a28:% rax, -0x30 (% rbp) ekle
...
Daha fazla ayrıntı için performans eğitimine bakın.
|
Bu soruyu ve cevaplarını yeni okudum ve bir cevabın eksik olduğunu hissediyorum.
Yönetilen dillerde özellikle iyi çalıştığını keşfettiğim dal tahminini ortadan kaldırmanın yaygın bir yolu, dal kullanmak yerine tablo aramadır (bu durumda test etmemiş olsam da).
Bu yaklaşım genel olarak şu durumlarda işe yarar:
küçük bir tablodur ve büyük olasılıkla işlemcide önbelleğe alınır ve
işleri oldukça sıkı bir döngüde çalıştırıyorsunuz ve / veya işlemci verileri önceden yükleyebilir.
Arka plan ve neden
İşlemci perspektifinden, hafızanız yavaştır. Hız farkını telafi etmek için, işlemcinize birkaç önbellek yerleştirilmiştir (L1 / L2 önbelleği). Güzel hesaplamalar yaptığınızı ve bir belleğe ihtiyacınız olduğunu anladığınızı hayal edin. İşlemci 'yükleme' işlemini alacak ve bellek parçasını önbelleğe yükleyecek ve ardından hesaplamaların geri kalanını yapmak için önbelleği kullanacaktır. Bellek nispeten yavaş olduğundan, bu 'yük' programınızı yavaşlatacaktır.
Dal tahmini gibi, bu Pentium işlemcilerde optimize edildi: işlemci, bir veri parçası yüklemesi gerektiğini tahmin ediyor ve işlem gerçekten önbelleğe çarpmadan önce bunu önbelleğe yüklemeye çalışıyor. Daha önce gördüğümüz gibi, dal tahmini bazen korkunç derecede yanlış gidiyor - en kötü senaryoda geri dönmeniz ve aslında sonsuza kadar sürecek bir bellek yüklemesi beklemeniz gerekir (başka bir deyişle: başarısız dal tahmini kötüdür, bir bellek bir dal tahmininin başarısız olmasından sonraki yük sadece korkunç!).
Neyse ki bizim için, eğer bellek erişim modeli tahmin edilebilirse, işlemci onu hızlı önbelleğine yükleyecektir ve her şey yolundadır.
Bilmemiz gereken ilk şey, neyin küçük olduğu? Daha küçük olması genellikle daha iyidir, ancak genel kural, <= 4096 bayt boyutunda olan arama tablolarına bağlı kalmaktır. Üst sınır olarak: Arama tablonuz 64K'dan büyükse, muhtemelen yeniden düşünmeye değer.
Bir masa inşa etmek
Böylece küçük bir masa oluşturabileceğimizi anladık. Yapılması gereken sonraki şey, yerinde bir arama işlevi almaktır. Arama işlevleri genellikle birkaç temel tamsayı işlemi (ve, veya, xor, shift, add, remove ve belki de çarpma) kullanan küçük işlevlerdir. Girişinizin arama işlevi tarafından tablonuzdaki bir tür 'benzersiz anahtara' çevrilmesini istersiniz, bu daha sonra size yapmak istediğiniz tüm işlerin yanıtını verir.
Bu durumda:> = 128, değeri koruyabileceğimiz anlamına gelir, <128, ondan kurtulacağımız anlamına gelir. Bunu yapmanın en kolay yolu bir 'VE' kullanmaktır: eğer onu tutarsak, 7FFFFFFF ile VE onu kullanırız; ondan kurtulmak istiyorsak, biz VE onu 0 ile yaparız. Ayrıca, 128'in 2'nin üssü olduğuna dikkat edin - böylece devam edip 32768/128 tamsayılardan oluşan bir tablo yapabilir ve onu bir sıfır ve bir sürü ile doldurabiliriz. 7FFFFFFFF'ler.
Yönetilen diller
Bunun yönetilen dillerde neden iyi çalıştığını merak edebilirsiniz. Sonuçta, yönetilen diller, karışmadığınızdan emin olmak için bir dal ile dizilerin sınırlarını kontrol eder ...
Pekala, tam olarak değil ... :-)
Yönetilen diller için bu dalın kaldırılması konusunda epeyce çalışma yapılmıştır. Örneğin:
for (int i = 0; i  = 128)? c: 0;
}
// Ölçek
DateTime startTime = System.DateTime.Now;
uzun toplam = 0;
for (int i = 0; i <100000; ++ i)
{
// Birincil döngü
for (int j = 0; j  = 128 değerleriyle ilgileniyoruz. Bu, bize bir değer isteyip istemediğimizi söyleyecek tek bir biti kolayca çıkarabileceğimiz anlamına gelir: kaydırarak Veriyi sağ 7 bit, 0 bit veya 1 bit ile bırakıyoruz ve sadece 1 bitimiz olduğunda değeri eklemek istiyoruz. Bu biti "karar biti" olarak adlandıralım.
Karar bitinin 0/1 değerini bir diziye indeks olarak kullanarak, veriler sıralı olsun veya olmasın eşit derecede hızlı olacak kod yapabiliriz. Kodumuz her zaman bir değer katacaktır, ancak karar biti 0 olduğunda, değeri umursamadığımız bir yere ekleyeceğiz. İşte kod:
// Ölçek
clock_t start = clock ();
uzun uzun a [] = {0, 0};
uzun uzun toplam;
için (işaretsiz i = 0; i <100000; ++ i)
{
// Birincil döngü
for (işaretsiz c = 0; c > 7);
a [j] + = veri [c];
}
}
çift ​​elapsedTime = statik_ yayın <çift> (saat () - başlangıç) / CLOCKS_PER_SEC;
toplam = a [1];
Bu kod, eklerin yarısını boşa harcar, ancak hiçbir zaman bir dal tahmin hatası vermez. Rastgele verilerde, gerçek bir if ifadesine sahip sürümden çok daha hızlıdır.
Ancak benim testimde, açık bir arama tablosu bundan biraz daha hızlıydı, çünkü muhtemelen bir arama tablosuna endeksleme, bit kaydırmadan biraz daha hızlıydı. Bu, kodumun arama tablosunu nasıl ayarladığını ve kullandığını gösterir (yaratıcı olmadan kodda "Arama Tablosu" için lut olarak adlandırılır). İşte C ++ kodu:
// Bildirin ve ardından arama tablosunu doldurun
int lut [256];
için (işaretsiz c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Arama tablosunu oluşturulduktan sonra kullanın
için (işaretsiz i = 0; i <100000; ++ i)
{
// Birincil döngü
for (işaretsiz c = 0; c  değeri)
düğüm = düğüm-> pLeft;
Başka
düğüm = düğüm-> pRight;
bu kütüphane şöyle bir şey yapacaktır:
i = (x  değer);
düğüm = düğüm-> bağlantı [i];
İşte bu koda bir bağlantı: Kırmızı Kara Ağaçlar, Ebediyen Kafası Karışık
|
Sıralanmış durumda, başarılı dal tahminine veya dalsız bir karşılaştırma numarasına güvenmekten daha iyisini yapabilirsiniz: dalı tamamen kaldırın.
Aslında dizi, veri <128 ve veri> = 128 olan bitişik bir bölgede bölümlenir. Bu nedenle, bölüm noktasını ikiye bölünmüş bir aramayla bulmalısınız (Lg (arraySize) = 15 karşılaştırmaları kullanarak), ardından düz bir toplama yapmalısınız o nokta.
Gibi bir şey (kontrol edilmemiş)
int i = 0, j, k = arraySize;
süre (i > 1;
eğer (veri [j]> = 128)
k = j;
Başka
i = j;
}
toplam = 0;
for (; i > 1;
for (i = 0, k = arraySize; i  = 128? k: i) = j)
j = (i + k) >> 1;
for (toplam = 0; i  = 128)
/ \
/ \
/ \
doğru yanlış
/ \
/ \
/ \
/ \
B) toplam + = veri [c]; C) döngü veya baskı için ().
Şube tahmini olmadan aşağıdakiler gerçekleşir:
B komutunu veya C komutunu yürütmek için, B komutuna veya C komutuna gitme kararı komut A'nın sonucuna bağlı olduğundan, işlemcinin A komutu boru hattında EX aşamasına ulaşmayana kadar beklemesi gerekecektir. böyle görünecek.
koşul true olursa:
Koşul yanlış döndürdüğünde:
A talimatının sonucunu beklemenin bir sonucu olarak, yukarıdaki durumda harcanan toplam CPU döngüsü (dallanma tahmini olmadan; hem doğru hem de yanlış için) 7'dir.
Peki dal tahmini nedir?
Şube tahmincisi, bu kesin olarak bilinmeden önce bir dalın (if-then-else yapısı) hangi yöne gideceğini tahmin etmeye çalışır. A talimatının boru hattının EX aşamasına gelmesini beklemeyecek, ancak kararı tahmin edecek ve bu talimata gidecektir (bizim örneğimizde B veya C).
Doğru bir tahmin durumunda, boru hattı şuna benzer:
Daha sonra tahminin yanlış olduğu tespit edilirse, kısmen yürütülen talimatlar atılır ve ardışık düzen, bir gecikmeye neden olarak doğru dal ile yeniden başlar.
Bir dal yanlış tahmininde boşa harcanan zaman, getirme aşamasından yürütme aşamasına kadar boru hattındaki aşamaların sayısına eşittir. Modern mikroişlemciler oldukça uzun boru hatlarına sahip olma eğilimindedir, bu nedenle yanlış tahmin gecikmesi 10 ila 20 saat döngüsü arasındadır. Ardışık düzen ne kadar uzun olursa, iyi bir branş öngörücüye olan ihtiyaç o kadar artar.
OP'nin kodunda, koşullu olduğunda ilk kez, dal tahmincisi tahmini temel alacak herhangi bir bilgiye sahip değildir, bu nedenle ilk kez rastgele bir sonraki talimatı seçecektir. Daha sonra for döngüsünde, tahmini geçmişe dayandırabilir.
Artan düzende sıralanmış bir dizi için üç olasılık vardır:
Tüm öğeler 128'den az
Tüm öğeler 128'den büyük
Bazı yeni başlayan öğeler 128'den azdır ve daha sonra 128'den büyük olur
Öngörücünün her zaman ilk çalıştırmada doğru dalı varsayacağını varsayalım.
Yani ilk durumda, her zaman doğru olanı alacakdal, çünkü tarihsel olarak tüm tahminleri doğrudur.
2. durumda, başlangıçta yanlış tahmin edecek, ancak birkaç yinelemeden sonra doğru tahmin edecektir.
3. durumda, öğeler 128'den az olana kadar başlangıçta doğru tahmin yapacaktır. Bundan sonra bir süre başarısız olacak ve geçmişte dal tahmin hatası gördüğünde kendisini düzeltecektir.
Tüm bu durumlarda, başarısızlık sayıca çok daha az olacaktır ve sonuç olarak, yalnızca birkaç kez kısmen yürütülen talimatları atıp doğru dalla baştan başlayarak daha az CPU döngüsüne yol açacaktır.
Ancak rastgele sıralanmamış bir dizi durumunda, tahminin kısmen yürütülen komutları atması ve çoğu zaman doğru dalla baştan başlaması ve sıralanmış diziye kıyasla daha fazla CPU döngüsüne neden olması gerekecektir.
|
Resmi bir cevap şundan olacaktır:
Intel - Şube Yanlış Tahmin Maliyetini Önleme
Intel - Yanlış Tahminleri Önlemek için Şube ve Döngü Yeniden Düzenleme
Bilimsel makaleler - Şube tahmin bilgisayar mimarisi
Kitaplar: J.L. Hennessy, D.A. Patterson: Bilgisayar mimarisi: nicel bir yaklaşım
Bilimsel yayınlardaki makaleler: T.Y. Evet, Y.N. Patt, şube tahminlerinde bunların çoğunu yaptı.
Ayrıca bu güzel diyagramdan şube tahmincisinin neden kafasının karıştığını da görebilirsiniz.
Orijinal koddaki her öğe rastgele bir değerdir
veri [c] = std :: rand ()% 256;
böylece tahminci std :: rand () darbesi gibi taraf değiştirecektir.
Öte yandan, sıralandıktan sonra, tahminci ilk olarak kesinlikle alınmamış bir duruma geçecek ve değerler yüksek değere dönüştüğünde tahminci üç seferde kesinlikle alınmadığından güçlü bir şekilde alınmayana kadar değişecektir.
|
Aynı satırda (bunun herhangi bir yanıtla vurgulanmadığını düşünüyorum) bazen (özellikle performansın önemli olduğu yazılımlarda - Linux çekirdeği gibi) aşağıdaki gibi if ifadeleri bulabileceğinizi belirtmek iyi olur:
eğer (muhtemelen (herşey_is_ok))
{
/* Bir şey yap */
}
veya benzer şekilde:
eğer (olası değil (very_improbable_condition))
{
/* Bir şey yap */
}
Hem olası () hem de olası olmayan () aslında GCC'nin __builtin_expect'i gibi bir şey kullanılarak tanımlanan makrolardır ve derleyicinin kullanıcı tarafından sağlanan bilgileri dikkate alarak koşulu tercih etmek için tahmin kodunu eklemesine yardımcı olur. GCC, çalışan programın davranışını değiştirebilecek veya önbelleği temizleme gibi düşük seviyeli talimatlar yayabilecek diğer yerleşikleri destekler. Mevcut GCC'nin yerleşikleri aracılığıyla geçen bu belgelere bakın.
Normalde bu tür optimizasyonlar, esas olarak gerçek zamanlı uygulamalarda veya yürütme süresinin önemli olduğu ve kritik olduğu gömülü sistemlerde bulunur. Örneğin, yalnızca 1/10000000 kez gerçekleşen bazı hata koşullarını kontrol ediyorsanız, derleyiciye bu konuda neden bilgi vermiyorsunuz? Bu şekilde, varsayılan olarak, şube tahmini koşulun yanlış olduğunu varsayacaktır.
|
C ++ 'da sık kullanılan Boole işlemleri, derlenen programda birçok dal üretir. Bu dallar döngülerin içindeyse ve tahmin edilmesi zorsa, yürütmeyi önemli ölçüde yavaşlatabilirler. Boole değişkenleri, yanlış için 0 ve doğru için 1 değeriyle 8 bitlik tamsayılar olarak saklanır.
Boole değişkenleri, giriş olarak Boole değişkenlerine sahip tüm operatörlerin, girişlerin 0 veya 1'den başka bir değere sahip olup olmadığını kontrol etmesi anlamında üst belirlenir, ancak çıkış olarak Boole'lere sahip operatörler, 0 veya 1'den başka bir değer üretemez. Girdi olarak Boole değişkenleri gerekenden daha az verimli.
Örnek düşünün:
bool a, b, c, d;
c = a && b;
d = a || b;
Bu genellikle derleyici tarafından aşağıdaki şekilde uygulanır:
bool a, b, c, d;
eğer (a! = 0) {
eğer (b! = 0) {
c = 1;
}
Başka {
CFALSE'a gidin;
}
}
Başka {
CFALSE:
c = 0;
}
eğer (a == 0) {
eğer (b == 0) {
d = 0;
}
Başka {
Goto DTRUE;
}
}
Başka {
DOĞRU:
d = 1;
}
Bu kod optimal olmaktan uzaktır. Yanlış tahminlerde şubeler uzun sürebilir. Boolean işlemleri, işlenenlerin 0 ve 1'den başka değerlere sahip olmadığı kesin olarak biliniyorsa çok daha verimli hale getirilebilir. Derleyicinin böyle bir varsayımda bulunmamasının nedeni, değişkenlerin başlatılmamışsa başka değerlere sahip olabileceğidir. veya bilinmeyen kaynaklardan geliyor. Yukarıdaki kod, a ve b geçerli değerlere başlatılmışsa veya Boolean çıkışı üreten operatörlerden geliyorsa optimize edilebilir. Optimize edilmiş kod şuna benzer:
char a = 0, b = 1, c, d;
c = a & b;
d = a | b;
Boole operatörleri (&& ve ||) yerine bitsel operatörlerin (& ve |) kullanılmasını mümkün kılmak için bool yerine char kullanılır. Bitsel operatörler, yalnızca bir saat döngüsü alan tek komutlardır. VEYA operatörü (|), a ve b'nin 0 veya 1'den başka değerleri olsa bile çalışır. VE operatörü (&) ve HARİÇ OR operatörü (^), işlenenler 0 ve 1'den başka değerlere sahipse tutarsız sonuçlar verebilir.
~ NOT için kullanılamaz. Yerine,0 veya 1 olduğu bilinen bir değişkeni 1 ile XOR'layarak Boolean NOT yapabilirsiniz:
bool a, b;
b =! a;
şunlar için optimize edilebilir:
char a = 0, b;
b = a ^ 1;
a && b, a yanlışsa değerlendirilmemesi gereken bir ifadeyse, a & b ile değiştirilemez (&&, b'yi değerlendirmez ve & will). Aynı şekilde, a || b, a ile değiştirilemez | b eğer b, a doğruysa değerlendirilmemesi gereken bir ifadeyse.
Bitsel işleçlerin kullanılması, işlenenler değişkense, işlenenler karşılaştırmalardansa daha avantajlıdır:
bool a; çift ​​x, y, z;
a = x> y && z <5.0;
çoğu durumda optimaldir (&& ifadesinin birçok dal yanlış kestirimi üretmesini beklemediğiniz sürece).
|
Kesinlikle!...
Dal tahmini, kodunuzda meydana gelen anahtarlama nedeniyle mantığın daha yavaş çalışmasını sağlar! Dümdüz bir caddeye veya çok sayıda dönüşün olduğu bir caddeye gidiyorsunuz gibi, tabii ki düz olan daha hızlı yapılacak! ...
Dizi sıralanırsa, koşulunuz ilk adımda yanlıştır: veri [c]> = 128, ardından sokağın sonuna kadar tüm yol için gerçek bir değer olur. Böylece mantığın sonuna daha hızlı ulaşırsınız. Öte yandan, sıralanmamış bir dizi kullanarak, kodunuzun kesinlikle daha yavaş çalışmasını sağlayan çok sayıda döndürme ve işleme ihtiyacınız vardır ...
Aşağıda sizin için oluşturduğum resme bakın. Hangi cadde daha hızlı bitecek?
Yani programlı olarak, şube tahmini, sürecin yavaşlamasına neden olur ...
Ayrıca sonunda, her biri kodunuzu farklı şekilde etkileyecek iki tür dal tahminimiz olduğunu bilmek güzel:
1. Statik
2. Dinamik
Statik dal tahmini, mikroişlemci tarafından ilk kez kullanılır
koşullu bir dalla karşılaşılır ve dinamik dal tahmini
koşullu şube kodunun sonraki yürütmeleri için kullanılır.
Bunlardan yararlanmak için kodunuzu etkili bir şekilde yazmak için
kurallar, if-else veya switch ifadelerini yazarken, en çok
önce yaygın vakalar ve en az yaygın olana kadar aşamalı olarak çalışır.
Döngüler için herhangi bir özel kod sıralaması gerekmez
yalnızca döngü yineleyicinin koşulu olarak statik dal tahmini
normalde kullanılır.
|
Bu soru zaten defalarca mükemmel bir şekilde yanıtlandı. Yine de grubun dikkatini başka bir ilginç analize çekmek istiyorum.
Son zamanlarda bu örnek (çok az değiştirildi), bir kod parçasının Windows'ta programın kendi içinde nasıl profillendirilebileceğini göstermenin bir yolu olarak da kullanıldı. Yol boyunca yazar, kodun hem sıralı hem de sıralanmamış durumda zamanının çoğunu nerede geçirdiğini belirlemek için sonuçları nasıl kullanacağını da gösterir. Son olarak parça, sıralanmamış durumda ne kadar dal yanlış kestiriminin gerçekleştiğini belirlemek için HAL'ın (Donanım Soyutlama Katmanı) az bilinen bir özelliğinin nasıl kullanılacağını da gösterir.
Bağlantı burada:
Kendinden Profil Oluşturma Gösterisi
|
Başkaları tarafından daha önce de belirtildiği gibi, gizemin arkasında Şube Tahmincisi var.
Bir şey eklemeye çalışmıyorum ama kavramı başka bir şekilde açıklıyorum.
Wiki'de metin ve diyagram içeren kısa bir giriş var.
Dal Tahminini sezgisel olarak geliştirmek için bir şema kullanan aşağıdaki açıklamayı beğendim.
Bilgisayar mimarisinde, dal tahmincisi bir
bir dalın hangi yönde olduğunu tahmin etmeye çalışan dijital devre (ör.
if-then-else yapısı) bu kesin olarak bilinmeden önce gidecektir.
şube tahmincisinin amacı, içindeki akışı iyileştirmektir.
talimat boru hattı. Şube belirleyicileri,
birçok modern boru hattında yüksek etkili performans elde etmek
x86 gibi mikroişlemci mimarileri.
İki yönlü dallanma genellikle koşullu bir sıçrama ile gerçekleştirilir
talimat. Koşullu bir sıçrama "alınmaz" ve devam eder
hemen ardından gelen ilk kod dalı ile yürütme
koşullu atlamadan sonra veya "alınabilir" ve bir
ikinci kod dalının olduğu program belleğinde farklı bir yer
saklanmış. Koşullu bir atlamanın olup olmayacağı kesin olarak bilinmemektedir.
durum hesaplanana kadar alınmış veya alınmamış ve
koşullu atlama, talimattaki yürütme aşamasını geçti
boru hattı (bkz. şekil 1).
Açıklanan senaryoya dayanarak, komutların farklı durumlarda bir boru hattında nasıl yürütüldüğünü göstermek için bir animasyon demosu yazdım.
Branch Predictor olmadan.
Şube tahmini olmadan, işlemcinin
koşullu atlama talimatı, yürütme aşamasını geçmeden önce
sonraki talimat boru hattındaki getirme aşamasına girebilir.
Örnek, üç komut içerir ve ilki, koşullu bir atlama talimatıdır. Son iki komut, koşullu atlama komutu yürütülene kadar boru hattına girebilir.
3 talimatın tamamlanması 9 saat döngüsü alacaktır.
Branch Predictor kullanın ve koşullu atlama yapmayın. Öngörünün,koşullu atlama.
3 talimatın tamamlanması 7 saat döngüsü alacaktır.
Branch Predictor'ı kullanın ve koşullu bir atlama yapın. Öngörünün koşullu sıçramayı almadığını varsayalım.
3 talimatın tamamlanması 9 saat döngüsü alacaktır.
Bir şube yanlış kestirimi durumunda boşa harcanan zaman şuna eşittir:
getirme aşamasından bitiş aşamasına kadar ardışık düzen içindeki aşamaların sayısı
yürütme aşaması. Modern mikroişlemciler oldukça uzun
yanlış tahmin gecikmesi 10 ile 20 saat arasında olacak şekilde boru hatları
döngüleri. Sonuç olarak, bir boru hattının daha uzun yapılması, bir
daha gelişmiş şube belirleyicisi.
Gördüğünüz gibi, Branch Predictor'ı kullanmamak için bir nedenimiz yok gibi görünüyor.
Branch Predictor'ın en temel kısmını açıklayan oldukça basit bir demo. Bu gifler can sıkıcıysa, lütfen bunları cevaptan çıkarın ve ziyaretçiler canlı demo kaynak kodunu BranchPredictorDemo'dan da alabilirler.
|
Dal-tahmin kazancı!
Dal yanlış tahminlerinin programları yavaşlatmadığını anlamak önemlidir. Kaçırılan bir tahminin maliyeti, dal tahmini yokmuş ve hangi kodun çalıştırılacağına karar vermek için ifadenin değerlendirilmesini beklemeniz gibidir (sonraki paragrafta daha fazla açıklama).
if (ifade)
{
// Çalıştırma 1
} Başka {
// Çalıştırma 2
}
Bir if-else \ switch ifadesi olduğunda, hangi bloğun yürütülmesi gerektiğini belirlemek için ifadenin değerlendirilmesi gerekir. Derleyici tarafından oluşturulan derleme kodunda, koşullu dallanma talimatları eklenir.
Bir dallanma talimatı, bir bilgisayarın farklı bir talimat dizisini yürütmeye başlamasına neden olabilir ve bu nedenle, bazı koşullara bağlı olarak, komutları sırayla yürütme varsayılan davranışından sapabilir (yani, ifade yanlışsa, program if bloğunun kodunu atlar), ki bizim durumumuzdaki ifade değerlendirmesidir.
Bununla birlikte, derleyici, gerçekte değerlendirilmeden önce sonucu tahmin etmeye çalışır. İf bloğundan talimatları alacak ve eğer ifade doğru çıkarsa harika! Onu değerlendirmek için gereken zamanı kazandık ve kodda ilerleme kaydettik; değilse o zaman yanlış kodu çalıştırırız, boru hattı temizlenir ve doğru blok çalıştırılır.
Görselleştirme:
Diyelim ki rota 1 veya rota 2'yi seçmeniz gerekiyor. Partnerinizin haritayı kontrol etmesini bekliyorum, ##'da durup beklediniz veya sadece rota1'i seçebilirdiniz ve şanslıysanız (rota 1 doğru rotadır), o zaman harika, partnerinizin haritayı kontrol etmesini beklemenize gerek kalmadı (haritayı kontrol etmek için harcayacağı zamandan tasarruf ettiniz), aksi takdirde sadece geri dönersiniz.
Boru hatlarını temizlemek çok hızlı olsa da, günümüzde bu kumarı almak buna değer. Sıralanmış verileri veya yavaş değişen verileri tahmin etmek, hızlı değişiklikleri tahmin etmekten her zaman daha kolay ve daha iyidir.
O Rota 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
Rota 2 \ --------------------------------
|
ARM'de dallanma gerekmez, çünkü her komut, İşlemci Durum Kaydında ortaya çıkabilecek 16 farklı koşuldan herhangi birini test eden (sıfır maliyetle) 4 bitlik bir koşul alanına sahiptir ve bir talimat üzerindeki koşul false, talimat atlandı. Bu, kısa dallanma ihtiyacını ortadan kaldırır ve bu algoritma için dal tahmini vuruşu olmaz. Bu nedenle, bu algoritmanın sıralı sürümü, fazladan sıralama ek yükü nedeniyle ARM'deki sıralanmamış sürümden daha yavaş çalışacaktır.
Bu algoritmanın iç döngüsü, ARM montaj dilinde aşağıdaki gibi görünecektir:
MOV R0, # 0 // R0 = toplam = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, veri // R2 = veri dizisinin adresi (bu talimatı dış döngünün dışına koyun)
.inner_loop // İç döngü dalı etiketi
LDRB R3, [R2, R1] // R3 = veri [c]
CMP R3, # 128 // R3 ile 128'i karşılaştırın
EKLE R0, R0, R3 // eğer R3> = 128 ise, o zaman + = veri [c] toplamına gerek yok!
EKLE R1, R1, # 1 // c ++
CMP R1, #arraySize // c'yi arraySize ile karşılaştırın
BLT inner_loop // c  ());
for (işaretsiz c = 0; c  = 128 ise
toplam = toplam + veri1 (j);
son
son
son
toc;
ExeTimeWithSorting = toc - tic;
Yukarıdaki MATLAB kodunun sonuçları aşağıdaki gibidir:
a: Geçen süre (sıralama olmadan) = 3479.880861 saniye.
b: Geçen süre (sıralama ile) = 2377.873098 saniye.
@GManNickG'deki gibi C kodunun sonuçları:
a: Geçen süre (sıralama olmadan) = 19.8761 sn.
b: Geçen süre (sıralama ile) = 7.37778 sn.
Buna dayanarak, MATLAB'ın sıralamasız C uygulamasından neredeyse 175 kat, sıralama ile 350 kat daha yavaş olduğu görülmektedir. Diğer bir deyişle, etki (dal tahmininin) MATLAB uygulaması için 1.46x ve C uygulaması için 2.7x'tir.
|
Verileri sıralamak için diğer yanıtların varsayımı doğru değildir.
Aşağıdaki kod dizinin tamamını değil, dizinin yalnızca 200 elemanlı bölümlerini sıralayarak en hızlı olanı çalıştırır.
Yalnızca k-öğesi bölümlerinin sıralanması, tüm diziyi sıralamak için gereken O (n.log (n)) zamanı yerine, doğrusal zamanda O (n) ön işlemeyi tamamlar.
#include 
#include 
#include 
int main () {
int data [32768]; const int l = veri boyutu / veri boyutu [0];
for (işaretsiz c = 0; c  = 128)
toplam + = veri [c];
}
}
std :: cout << static_cast  (clock () - başlangıç) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "sum =" << toplam << std :: endl;
}
Bu aynı zamanda sıralama düzeni gibi herhangi bir algoritmik sorunla ilgisi olmadığını "kanıtlar" ve aslında dal tahminidir.
|
Bjarne Stroustrup'un bu soruya cevabı:
Bu bir röportaj sorusuna benziyor. Bu doğru mu? Nasıl bilebilirsin Önce bazı ölçümler yapmadan verimlilikle ilgili soruları yanıtlamak kötü bir fikirdir, bu nedenle nasıl ölçüleceğini bilmek önemlidir.
Bu yüzden, bir milyon tam sayı vektörüyle denedim ve şunu elde ettim:
Zaten 32995 milisaniye sıralandı
125944 milisaniye karıştırıldı
Zaten 18610 milisaniye sıralandı
133304 milisaniye karıştırıldı
Zaten 17942 milisaniye sıralandı
107858 milisaniye karıştırıldı
Emin olmak için birkaç kez koştum. Evet, fenomen gerçektir. Anahtar kodum şuydu:
void run (vektör  & v, const string & label)
{
auto t0 = system_clock :: şimdi ();
sort (v.begin (), v.end ());
auto t1 = system_clock :: şimdi ();
cout << etiketi
<< duration_cast  (t1 - t0) .count ()
<< "milisaniye \ n";
}
void tst ()
{
vektör  v (1'000'000);
iota (v.begin (), v.end (), 0);
run (v, "önceden sıralanmış");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
run (v, "karıştırılmış");
}
En azından bu derleyici, standart kitaplık ve optimize edici ayarlarıyla fenomen gerçektir. Farklı uygulamalar farklı yanıtlar verebilir ve verir. Aslında, birisi daha sistematik bir çalışma yaptı (hızlı bir web araması bulacaktır) ve çoğu uygulama bu etkiyi göstermektedir.
Bunun bir nedeni dal tahminidir: sıralama algoritmasındaki anahtar işlem "if (v [i]  = 128 değerlerine önem veriyoruz. Bu, bize bir değer isteyip istemediğimizi söyleyecek tek bir biti kolayca çıkarabileceğimiz anlamına gelir: kaydırarak Veriyi sağ 7 bit, 0 bit veya 1 bit ile bırakıyoruz ve sadece 1 bitimiz olduğunda değeri eklemek istiyoruz. Bu biti "karar biti" olarak adlandıralım.
Karar bitinin 0/1 değerini bir diziye indeks olarak kullanarak, veriler sıralı olsun veya olmasın eşit derecede hızlı olacak kod yapabiliriz. Kodumuz her zaman bir değer katacaktır, ancak karar biti 0 olduğunda, değeri umursamadığımız bir yere ekleyeceğiz. İşte kod:
// Ölçek
clock_t start = clock ();
uzun uzun a [] = {0, 0};
uzun uzun toplam;
için (işaretsiz i = 0; i <100000; ++ i)
{
// Birincil döngü
for (işaretsiz c = 0; c > 7);
a [j] + = veri [c];
}
}
çift ​​elapsedTime = statik_ yayın <çift> (saat () - başlangıç) / CLOCKS_PER_SEC;
toplam = a [1];
Bu kod, eklerin yarısını boşa harcar, ancak hiçbir zaman bir dal tahmin hatası vermez. Rastgele verilerde, gerçek bir if ifadesine sahip sürümden çok daha hızlıdır.
Ancak benim testimde, açık bir arama tablosu bundan biraz daha hızlıydı, çünkü muhtemelen bir arama tablosuna endeksleme, bit kaydırmadan biraz daha hızlıydı. Bu, kodumun arama tablosunu nasıl ayarladığını ve kullandığını gösterir (yaratıcı olmadan kodda "Arama Tablosu" için lut olarak adlandırılır). İşte C ++ kodu:
// Bildirin ve ardından arama tablosunu doldurun
int lut [256];
için (işaretsiz c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Arama tablosunu oluşturulduktan sonra kullanın
için (işaretsiz i = 0; i <100000; ++ i)
{
// Birincil döngü
for (işaretsiz c = 0; c  değeri)
düğüm = düğüm-> pLeft;
Başka
düğüm = düğüm-> pRight;
bu kütüphane şöyle bir şey yapacaktır:
i = (x  değer);
düğüm = düğüm-> bağlantı [i];
Bu güzel bir çözüm ve belki işe yarayacaktır.
|
Oldukça aktif soru. Bu soruyu cevaplamak için 10 itibar kazanın. İtibar koşulu, bu sorunun istenmeyen postalardan ve yanıtlanmayan etkinliklerden korunmasına yardımcı olur.
Aradığın cevap değil mi? Java c ++ performans optimizasyonu dal tahmini etiketli diğer sorulara göz atın veya kendi sorunuzu sorun.